/// https://leetcode-cn.com/problems/next-permutation
pub struct Solution;

impl Solution {
    pub fn next_permutation_early_return(nums: &mut Vec<i32>) {
        let n = nums.len();
        let mut i: usize = n - 1;

        for j in (0..n).rev() {
            if j > 0 && nums[j] > nums[j - 1] {
                while nums[j - 1] >= nums[i] {
                    i -= 1;
                }
                nums.swap(j - 1, i);
                nums[j..].reverse();
                return;
            } else if j == 0 {
                nums.reverse();
                return;
            }
        }
    }

    pub fn next_permutation(nums: &mut Vec<i32>) {
        let n = nums.len();
        let mut j = n - 1;
        while j > 0 && nums[j - 1] >= nums[j] {
            j -= 1;
        }
        if j > 0 {
            let mut i = n - 1;
            while nums[j - 1] >= nums[i] {
                i -= 1;
            }
            nums.swap(j - 1, i);
        }
        nums[j..].reverse();
    }

    pub fn next_permutation_gym(nums: &mut Vec<i32>) {
        let n = nums.len();
        let mut i = n - 1;
        while i > 0 && nums[i - 1] >= nums[i] {
            i -= 1;
        }
        let mut j = i;
        let mut k = n - 1;
        println!("");
        while j < k {
            vec_pos!(nums; j,k);
            nums.swap(j, k);
            j += 1;
            k -= 1;
        }
        if i > 0 {
            vec_pos!(nums; i,k);
            k = i;
            i -= 1;
            while nums[k] <= nums[i] {
                k += 1;
            }
            nums.swap(i, k)
        }
    }

    pub fn next_permutation_iterator(nums: &mut Vec<i32>) {
        let to_swap = nums.windows(2).enumerate().rev().find(|&(_, w)| w[0] < w[1]);

        if let Some((i, w)) = to_swap {
            let v = w[0];
            let j = nums.iter().enumerate().rev().find(|(_, x)| **x > v).unwrap().0;
            nums.swap(i, j);
            nums[i + 1..].reverse();
        } else {
            nums.reverse();
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn assert(f: impl Fn(&mut Vec<i32>)) {
        let mut nums = vec![1, 2, 3, 4];
        f(&mut nums);
        assert_eq!(nums, vec![1, 2, 4, 3]);

        let mut nums = vec![1, 2, 4, 3];
        f(&mut nums);
        assert_eq!(nums, vec![1, 3, 2, 4]);

        let mut nums = vec![5, 3, 1, 4, 2];
        f(&mut nums);
        assert_eq!(nums, vec![5, 3, 2, 1, 4]);

        let mut nums = vec![3, 2, 1];
        f(&mut nums);
        assert_eq!(nums, vec![1, 2, 3]);

        let mut nums = vec![1, 1, 5];
        f(&mut nums);
        assert_eq!(nums, vec![1, 5, 1]);

        let mut nums = vec![4, 4, 4, 3, 1];
        f(&mut nums);
        assert_eq!(nums, vec![1, 3, 4, 4, 4]);

        let mut nums = vec![2, 4, 4, 4, 3, 1];
        f(&mut nums);
        assert_eq!(nums, vec![3, 1, 2, 4, 4, 4]);

        let mut nums = vec![1, 2, 3, 1, 1,];
        f(&mut nums);
        assert_eq!(nums, vec![1, 3, 1, 1, 2]);

        let mut nums = vec![5, 4, 7, 5, 3, 2];
        f(&mut nums);
        assert_eq!(nums, vec![5, 5, 2, 3, 4, 7]);
    }

    bench!(assert Solution::next_permutation_iterator);
    bench!(assert Solution::next_permutation_early_return);
    bench!(assert Solution::next_permutation);
    bench!(assert Solution::next_permutation_gym);
}
